#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

struct ListNode
{
    struct ListNode* next;
    int val;
};

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
    struct ListNode* list1 = headA;
    struct ListNode* list2 = headB;

    int a = 0, b = 0;
    while (list1)
    {
        list1 = list1->next;
        a++;
    }

    while (list2)
    {
        list2 = list2->next;
        b++;
    }

    int gap = abs(a - b);

    if (a < b)
    {
        list1 = headB;
        list2 = headA;
    }
    else
    {
        list1 = headA;
        list2 = headB;
    }

    while (gap)
    {
        list1 = list1->next;
        gap--;
    }

    while (list1 && list2)
    {
        if (list1 == list2)
        {
            return list1;
        }
        list1 = list1->next;
        list2 = list2->next;
    }

    return NULL;
}

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    if (headA == NULL || headB == NULL) {
        return NULL;
    }
    struct ListNode* pA = headA, * pB = headB;
    while (pA != pB) {
        pA = pA == NULL ? headB : pA->next;
        pB = pB == NULL ? headA : pB->next;
    }
    return pA;
}

typedef char StDataType;
typedef struct Stack
{
    StDataType* s;
    int top;
    int capcity;
}St;

void StInit(St* pst)
{
    assert(pst);
    pst->s = NULL;
    pst->top = 0;
    pst->capcity = 0;
}

void StDestroy(St* pst)
{
    assert(pst);
    free(pst->s);
    pst->s = NULL;
    pst->top = 0;
    pst->capcity;
}

void StPush(St* pst, StDataType x)
{
    assert(pst);
    if (pst->top == pst->capcity)
    {
        int newcapcity = pst->capcity == 0 ? 4 : pst->capcity * 2;
        StDataType* tmp = (StDataType*)realloc(pst->s, sizeof(StDataType) * newcapcity);
        if (tmp == NULL)
        {
            perror("realloc fail");
            return;
        }
        pst->s = tmp;
        pst->capcity = newcapcity;
    }
    pst->s[pst->top] = x;
    pst->top++;
}

bool StEmpty(St* pst)
{
    assert(pst);
    return pst->top == 0;
}

void StPop(St* pst)
{
    assert(pst);
    assert(pst->top > 0);
    pst->top--;
}

StDataType StTop(St* pst)
{
    assert(pst);
    assert(pst->top > 0);
    return pst->s[pst->top - 1];
}




bool isValid(char* s)
{
    St pst;
    StInit(&pst);
    while (*s)
    {
        if (*s == '(' || *s == '[' || *s == '{')
        {
            StPush(&pst, *s);
        }
        else
        {
            if (StEmpty(&pst))
            {
                StDestroy(&pst);
                return false;
            }

            char a = StTop(&pst);
            StPop(&pst);
            if ((*s == ')' && a != '(')
                || (*s == ']' && a != '[')
                || (*s == '}' && a != '{'))
            {
                StDestroy(&pst);
                return false;
            }
        }
        s++;
    }
    bool ret = StEmpty(&pst);
    StDestroy(&pst);
    return ret;
}